{
ID : phamnamlo2
PROB : cheappal
LANG : PASCAL
}

program CHEAPPAL;
const
  fi = 'cheappal.in';
  fo = 'cheappal.out';
  max = 2000;
var
  s : array[1..max] of char;
  d : array[1..max, 1..max] of longint;
  cost : array['a'..'z'] of longint;
  m, n : longint;

function min(x, y : longint) : longint;
begin
  if x < y then min := x
  else min := y;
end;

procedure inp;
var
  i, add, del : longint;
  k : char;
begin
  readln(n, m);
  for i := 1 to m do read(s[i]);
  readln;
  for i := 1 to n do
  begin
    readln(k, add, del);
    cost[k] := min(add, del);
  end;
end;

procedure init;
var
  i : longint;
begin
  for i := 1 to m do d[i, i] := 0;
end;

procedure process;
var
  i, j, l : longint;
begin
  init;
  for l := 2 to m do
    for i := 1 to m-l+1 do
    begin
      j := i+l-1;
      if s[i] = s[j] then d[i, j] := d[i+1, j-1]
      else d[i, j] := min(d[i+1, j] + cost[s[i]], d[i, j-1] + cost[s[j]]);
    end;
end;

procedure out;
begin
  writeln(d[1, m]);
end;

begin
  assign(input, fi); reset(input);
  assign(output, fo); rewrite(output);

  inp;
  process;
  out;

  close(output);
  close(input);
end.
